// Copyright (C) 2012 Yury Bychenkov (http://bychenkov.com).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//  - Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//  - Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//  - Neither the name of Yury Bychenkov nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "query.h"
#include "parser.h"
#include "traits.h"

Logger QueryCompiler::logger("QueryCompiler");


ASTNode::ASTNode(uint type_, const void* data_, uint size_):
	type(type_)	
{
	data.reserve(size_);
	for (uint i = 0; i < size_; i++) {
		data.push_back(((const uint8*) data_)[i]);
	}
}

ASTNode::ASTNode(uint type_, ASTNode* child1):
	type(type_)
{
	children.push_back(child1);
}

ASTNode::ASTNode(uint type_, ASTNode* child1, ASTNode* child2):
	type(type_)
{
	children.push_back(child1);
	children.push_back(child2);
}

ASTNode::~ASTNode() {
	for (uint i = 0; i < children.size(); i++) {
		if (children[i] != 0) {
			delete children[i];
		}
	}
}

void ASTNode::print(int level) {
	char s[] = "                                                                                            ";
	s[level*4] = 0;
	cout << s << type << " {" << endl;
	for (uint i = 0; i < children.size(); i++) {
		children[i]->print(level + 1);
	}
	cout << s << "}" << endl;
}


Query::Query(const Schema& schema_, const uint16* code_, uint codeCount_, uint topCount_, const vector<Projection>& projections_, const vector<Order>& ordering_, const ResourceBundle& data_):
	schema(schema_),
	code(0),
	codeCount(codeCount_),
	topCount(topCount_),
	projections(projections_),
	ordering(ordering_),
	data(data_)
{	
	if (codeCount_ > 0) {
		code = new uint16 [codeCount_];
		memcpy(code, code_, codeCount_ * sizeof(uint16));
	}
}

Query::~Query() {
	if (code != 0) {
		delete [] code;
	}
}

vector<uint> Query::getTupleColumns() const {
	vector<uint> columnIndecies;
	for (uint i = 0; i < ordering.size(); i++) {
		columnIndecies.push_back(ordering[i].columnIndex);
	}
	for (uint i = 0; i < projections.size(); i++) {
		if (find(columnIndecies.begin(), columnIndecies.end(), projections[i].columnIndex) == columnIndecies.end()) {
			columnIndecies.push_back(projections[i].columnIndex);
		}
	}
	return columnIndecies;
}


QueryCompiler::QueryCompiler(const Schema& schema_): 
	schema(schema_),
	root(0), 
	parser(0) 
{
}

QueryCompiler::~QueryCompiler() {
	if (root != 0) {
		delete root;
	}
}


void QueryCompiler::fail(const char* m) {
	failed = true;
	message = m;
	message += ": ";
}

void QueryCompiler::success(ASTNode* node) {
	root = node;
}

bool QueryCompiler::parse(const char* query) {
	const char* s = query;

	begin();

	while (!failed) {
		char ch = *s++;

		if (ch == '\0') {
			break;
		}

		if (ch == ' ' || ch == '\r' || ch == '\r' || ch == '\n') {
			continue;
		}

		if (ch == ',') {
			push(TK_COMMA);
			continue;
		}

		if (ch == '(') {
			push(TK_LPAR);
			continue;
		}

		if (ch == ')') {
			push(TK_RPAR);
			continue;
		}

		if (ch == '<') {
			if (*s == '=') {
				s++;
				push(TK_LE);
			} else if (*s == '>') {
				s++;
				push(TK_NE);
			} else {
				push(TK_LT);
			}
			continue;
		}

		if (ch == '>') {
			if (*s == '=') {
				s++;
				push(TK_GE);
			} else {
				push(TK_GT);
			}
			continue;
		}

		if (ch == '=') {
			push(TK_EQ);
			continue;
		}

		if ((ch == '_') || ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z')) {
			const char* p = s - 1;
			while (('0' <= *s && *s <= '9') || ('a' <= *s && *s <= 'z') || ('A' <= *s && *s <= 'Z') || (*s == '_') || (*s == '.')) {
				s++;
			}

			char* name = new char[s - p + 1];
			char* r = name;
			while (p < s) {
				*r++ = tolower(*p++);
			}
			*r = '\0';

			if (0 == strcmp("and", name)) {
				push(TK_AND, name);
			} else if (0 == strcmp("or", name)) {
				push(TK_OR, name);
			} else if (0 == strcmp("not", name)) {
				push(TK_NOT, name);
			} else if (0 == strcmp("null", name)) {
				push(TK_NULL, name);
			} else if (0 == strcmp("select", name)) {
			    push(TK_SELECT, name);
			} else if (0 == strcmp("top", name)) {
			    push(TK_TOP, name);
			} else if (0 == strcmp("where", name)) {
			    push(TK_WHERE, name);
			} else if (0 == strcmp("order", name)) {
				push(TK_ORDER, name);
			} else if (0 == strcmp("by", name)) {
				push(TK_BY, name);
			} else if (0 == strcmp("asc", name)) {
				push(TK_ASC, name);
			} else if (0 == strcmp("desc", name)) {
				push(TK_DESC, name);
			} else {
				string columnName(name);
				uint type = !schema.hasColumn(columnName) ? Schema::UNKNOWN : schema.getColumnByName(columnName).type;
				if (type == Schema::STRING) {
					push(TK_STRING_ID, name);
				} else if (type == Schema::INTEGER) {
					push(TK_INTEGER_ID, name);
				} else if (type == Schema::DECIMAL) {
					push(TK_DECIMAL_ID, name);
				} else {
					delete [] name;
					fail("Unknown column");
					break;
				}
			}

			continue;
		} else if (('0' <= ch && ch <= '9') || (ch == '+') || (ch == '-')) {
			s--;
			const char* p = 0;

			uint8 buffer[DecimalTraits::MAX_ELEMENT_SIZE];

			int size = NumberUtil::parseDecimal(s, buffer, DecimalTraits::MAX_ELEMENT_SIZE, &p);
			if (size == 0) {
				fail("Wrong number format");
				break;
			} else if (size < 0) {
				fail("Decimal overflow");
				break;
			}

			const char* r = s + 1;
			while (r < p && ('0' <= *r && *r <= '9')) {
				r++;
			}

			if (r < p) {
				uint8* value = new uint8[size + DecimalTraits::MAX_OVERHEAD_SIZE];
				DecimalTraits::encode(buffer, size, value, size + DecimalTraits::MAX_OVERHEAD_SIZE);
				push(TK_DECIMAL_LITERAL, value);				
			} else {
				int64 v;
				if (!NumberUtil::parseInteger(s, v)) {
					fail("Integer overflow");
					break;					
				}

				uint8* value = new uint8[IntegerTraits::MAX_ENCODED_SIZE];
				IntegerTraits::encode(v, value);
				push(TK_INTEGER_LITERAL, value);				
			}

			s = p;

			continue;			
		} else if (ch == '\'') {
			const char* p = s;
			while (*s != '\0') {
				if (s[0] == '\'') {
					if (s[1] != '\'') {
						break;
					}
					s++;
				}
				s++;
			}

			if (*s == '\0') {
				s = p - 1;
				fail("Missing a closing quote");
				break;
			}
			char* v = new char[s - p];
			char* r = v;
			while (p < s) {
				*r++ = *p++;
				if (*p == '\'') {
					p++;
				}
			}
			s++;

			uint8* value = new uint8 [r - v + StringTraits::MAX_OVERHEAD_SIZE];
			StringTraits::encode((const uint8*) v, r - v, value, r - v + StringTraits::MAX_OVERHEAD_SIZE);
			delete [] v;

			push(TK_STRING_LITERAL, value);
			continue;
		}

		fail("Unsupported token");
		s--;
	}

	if (!failed) {
		push(0);
	}

	if (failed) {
		message += string(query, s - query);
		message += "^^^";
		message += s;
		logger.error(message);
	}

	end();

  	parser = 0;

  	return !failed;
}



Query* QueryCompiler::compile(const Schema& schema, const char* queryString) {
	return QueryCompiler(schema).compile(queryString);

}

Query* QueryCompiler::compile(const char* queryString) {
	if (!parse(queryString)) {
		return 0;
	}

	if (root == 0) {
		return 0;
	}

	code.push_back(BC_RET_FALSE);
	code.push_back(BC_RET_TRUE);

	for (uint i = 0, count = schema.getColumnCount(); i < count; i++) {
		bundle.add(0, 0);
	}

	uint topCount = 0;
	vector<Query::Projection> projections;
	vector<Query::Order> ordering;

	for (uint i = 0; i < root->children.size(); i++) {
		ASTNode* child = root->children[i];
		
		if (child->type == ASTNode::SELECT) {
			for (uint j = 0; j < child->children.size(); j++) {
				if (child->children[j]->type == ASTNode::TOP) {
					ASTNode* top = child->children[j];
					int64 v = IntegerTraits::decode(&top->children[0]->data[0]);
					topCount = v <= 0 ? 0 : (uint) v;
			 	} else {
					Query::Projection p;
					p.columnIndex = addRef(child->children[j]);
					projections.push_back(p);
			   }
			}
		} else if (child->type == ASTNode::WHERE) {
			if (!compile(child->children[0], 0, 1)) {
				return 0;
			}
		} else if (child->type == ASTNode::ORDER_BY) {
			for (uint j = 0; j < child->children.size(); j++) {
				Query::Order o;
				o.columnIndex = addRef(child->children[j]->children[0]);
				o.asc = child->children[j]->type == ASTNode::ASC;
				ordering.push_back(o);
			}
		}
	}

	reverse(code.begin(), code.end());

	if (topCount == 0 && ordering.size() > 0) {
		topCount = DEFAULT_TOP_COUNT;
		logger.warn("Top count set to default: ", topCount);
	} else if (topCount > MAX_TOP_COUNT) {
		topCount = MAX_TOP_COUNT;
		logger.warn("Top count truncated to max: ", topCount);
	}

	return new Query(schema, &code[0], code.size(), topCount, projections, ordering, bundle);
}

bool QueryCompiler::compile(const ASTNode* node, uint falseJoint, uint trueJoint) {

	int nodeType = node->type;
	uint offset = code.size();

	switch (nodeType) {
		case ASTNode::AND:
			for (int i = node->children.size() - 1; i >= 0; i--) {
				if (!compile(node->children[i], falseJoint, trueJoint)) {
					return false;
				}
				trueJoint = code.size() - 1;
			}
			return true;

		case ASTNode::OR:
			for (int i = node->children.size() - 1; i >= 0; i--) {
				if (!compile(node->children[i], falseJoint, trueJoint)) {
					return false;
				}
				falseJoint = code.size() - 1;
			}
			return true;

		case ASTNode::EQ:
		case ASTNode::LT:
		case ASTNode::LE:
		case ASTNode::GT:
		case ASTNode::GE:
		case ASTNode::NE:

			uint16 opcode;
			uint16 joint;

			if (falseJoint == offset - 1) {
				opcode = nodeType - ASTNode::EQ + BC_EQ_I;
				joint = trueJoint;
			} else if (trueJoint == offset - 1) {
				opcode = ASTNode::NE - nodeType + BC_EQ_I;
				joint = falseJoint;				
			} else {
				return false;
			}

			
			const ASTNode* child1 = node->children[0];
			const ASTNode* child2 = node->children[1];

			uint ref1 = addRef(child1);
			uint ref2 = addRef(child2);


			code.push_back(offset + 1 - joint);
			code.push_back(BC_IF);

			code.push_back(0);
			code.push_back(0);
			code.push_back(0);
			code.push_back(ref2);
			code.push_back(ref1);
			code.push_back(opcode);

			return true;
	}

	return false;
}

uint QueryCompiler::addRef(const ASTNode* node) {
	switch (node->type) {
		case ASTNode::STRING_ID:
		case ASTNode::INTEGER_ID:
		case ASTNode::DECIMAL_ID: {
			string name((const char*)&node->data[0], node->data.size());

			return !schema.hasColumn(name)? 0: schema.getColumnByName(name).index;
		}

		case ASTNode::STRING_VALUE:
		case ASTNode::INTEGER_VALUE:
		case ASTNode::DECIMAL_VALUE: {
			uint size = node->data.size();
			if (size == 0) {
				bundle.add(0, 0);
			} else {
				bundle.add(&node->data[0], size);
			}
			return bundle.getSize() - 1;
		}
	}	

	return 0;
}
